{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.1-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果不考虑完全二叉树这个条件\n",
    "\n",
    "时间复杂度：$O(n)$\n",
    "\n",
    "空间复杂度：$O(d) = O(\\log(n))$，其中 d 指的是树的的高度，运行过程中堆栈所使用的空间。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from leetcode_test import TreeNode\n",
    "class Solution:\n",
    "    def countNodes(self, root: TreeNode) -> int:\n",
    "        return 1 + self.countNodes(root.right) + self.countNodes(root.left) if root else 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果考虑完全二叉树这个条件，可以leetcode官方的题解\n",
    "\n",
    "* [完全二叉树的节点个数 - 完全二叉树的节点个数 - 力扣（LeetCode）](https://leetcode-cn.com/problems/count-complete-tree-nodes/solution/wan-quan-er-cha-shu-de-jie-dian-ge-shu-by-leetcode/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如何确定，最后一个元素的位置，检查一次，需要的复杂度是 $O(d)$ ,最多需要检查 `d` 次， 时间复杂度为 $O(d^2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如何求二叉树的深度？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_depth(node):\n",
    "    depth = 0\n",
    "    while node.left:\n",
    "        node = node.left\n",
    "        depth += 1\n",
    "    return depth\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "1"
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t = TreeNode.create([1,2])\n",
    "compute_depth(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如何检查最后一个节点的位置？\n",
    "\n",
    "一共有$2^d - 1$ 个节点， 我们需要在 $2^{d-1}$ 到 $2^d - 1$ 之间搜索"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def exists(idx: int, d: int, node: TreeNode) -> bool:\n",
    "    \"\"\"\n",
    "    idx 为最后一层，从左到右数，第几个(从0开始)\n",
    "    d   为二叉树的层树，从0开始\n",
    "\n",
    "    \"\"\"\n",
    "    left, right = 0, 2**d - 1\n",
    "    for _ in range(d):\n",
    "        pivot = left + (right - left) // 2\n",
    "        if idx <= pivot:\n",
    "            node = node.left\n",
    "            right = pivot\n",
    "        else:\n",
    "            node = node.right\n",
    "            left = pivot + 1\n",
    "    print(node)\n",
    "    return node is not None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "<TreeNode: 6>\n"
    },
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t = TreeNode.create([1,2,3,4,5,6])\n",
    "d = compute_depth(t)\n",
    "exists(2, d-1, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countNodes(root: TreeNode) -> int:\n",
    "    # if the tree is empty\n",
    "    if not root:\n",
    "        return 0\n",
    "    \n",
    "    d = compute_depth(root)\n",
    "    # if the tree contains 1 node\n",
    "    if d == 0:\n",
    "        return 1\n",
    "    \n",
    "    # Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).\n",
    "    # Perform binary search to check how many nodes exist.\n",
    "    left, right = 1, 2**d - 1\n",
    "    while left <= right:\n",
    "        pivot = left + (right - left) // 2\n",
    "        if exists(pivot, d, root):\n",
    "            left = pivot + 1\n",
    "        else:\n",
    "            right = pivot - 1\n",
    "    \n",
    "    # The tree contains 2**d - 1 nodes on the first (d - 1) levels\n",
    "    # and left nodes on the last level.\n",
    "    return (2**d - 1) + left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "<TreeNode: 6>\nNone\n"
    },
    {
     "data": {
      "text/plain": "6"
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t = TreeNode.create([1,2,3,4,5,6])\n",
    "countNodes(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}